package DynamicProgramming;

public class p96 {
    class Solution {
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= n; i++){//总的结点数
                for(int j = 1; j <= i; j++){
                    //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
                    //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                    dp[i] += dp[i - j] * dp[j - 1];
                }
            }
            return dp[n];
        }
    }
}
